﻿// 3382. 整数拆分.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/3385/


一个整数总可以拆分为 2 的幂的和。

例如：7 可以拆分成

7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,

7=1+1+1+1+1+2,7=1+1+1+1+1+1+1

共计 6 种不同拆分方式。

再比如：4 可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2。

用 f(n) 表示 n 的不同拆分的种数，例如 f(7)=6。

要求编写程序，读入 n，输出 f(n)mod109。

输入格式
一个整数 n。

输出格式
一个整数，表示 f(n)mod109。

数据范围
1≤N≤106
输入样例：
7
输出样例：
6
*/




#include <iostream>

using  namespace std;

const int N = 1000010;
long long dp[N];
int n;
const int MOD = 1000000000;

int main() {
    cin >> n;
    dp[0] = 1;

    for (int i = 1; i <= n; i <<= 1) {
        for (int j = 1; j <= n; j++) {
            if (j >= i) {
                dp[j] += dp[j - i];
                dp[j] %= MOD;
            }
        }
    }

    cout << dp[n] << endl;

    return 0;
}
